P4056 [JSOI2009]火星藏宝图

首先有一个非常 naive 的 O(n2)\mathcal{O(n^2)} dp。

dpidp_i 表示到第 ii 座岛的最大收益,那么有:

dpi=max1jn,j=i,xjxi,yjyi{dpj(xixj)2(yiyj)2}+vidp_i=\max_{1\le j \le n, j \not= i ,x_j \le x_i ,y_j \le y_i }\{dp_j-(x_i-x_j)^2-(y_i-y_j)^2\}+v_i

然后你按坐标排序,遇到纵坐标大于当前岛的直接剪掉。

这样就有 60 pts 了。

因为有坐标限制所以不好优化,考虑另一种 dpdp

dpi,jdp_{i,j} 表示走到 (i,j)(i,j) 的最大收益,如果没有岛为极小值。

那么转移为:

dpi,j=max1ki,1lj{dpk,l+(ik)2+(jl)2}+vi,jdp_{i,j}=\max_{1 \le k \le i , 1 \le l \le j} \{dp_{k,l}+(i-k)^2+(j-l)^2\}+v_{i,j}

dpi,j=max1ki,1lj{dpk,l+k22ik+l22jl}+vi,j+i2+j2dp_{i,j}=\max_{1 \le k \le i , 1 \le l \le j} \{dp_{k,l}+k^2-2ik+l^2 -2jl\}+v_{i,j}+i^2+j^2

这样我们就成功把 O(n2)\mathcal{O(n^2)} 优化转换为 O(m4)\mathcal{O(m^4)} 了。

这是一个二维斜率优化,令 (j1,j2)(j_1,j_2) 优于 (k1,k2)(k_1,k_2) ,那么有:

dpj1,j2+j122ij1+j222jj2<dpk1,k2+k122ik1+k222jk2dp_{j_1,j_2}+{j_1}^2-2ij_1+{j_2}^2 -2j{j_2} < dp_{k_1,k_2}+{k_1}^2-2ik_1+{k_2}^2 -2j{k_2}

(dpj1,j2+j12+j22)(dpk1,k2+k12+k22)<2i(j1k1)+2j(j2k2)(dp_{j_1,j_2}+{j_1}^2+{j_2}^2)-(dp_{k_1,k_2}+{k_1}^2+{k_2}^2) < 2i(j_1-k_1) +2j(j_2 -k_2)